package alo.p19;

/**
 * @ClassName MatrixChainOrder
 * @Description 矩阵乘积括号化——使得乘法运算的次数最少
 * @Author Fanxc
 * @DATE 2021/3/15 16:26
 * @Version 1.0
 */
public class MatrixChainOrder {
    void matrixChainOrder(int[] P,int length){
        int n=length-1;
        int[][] M=new int[n][n];
        int[][] S=new int[n][n];//保存分割点，用于回溯
        for (int i = 0; i < n; i++) {
            M[i][i]=0;
        }
        for (int l = 2; l <= n; l++) {//l表示的是链的长度
            for (int i = 1; i <= n-l+1; i++) {
                int j=i+l-1;
                M[i][j]=Integer.MAX_VALUE;//初始化为最大
                for (int k = i; k < j; k++) {
                    int thisCost=M[i][k]+M[k+1][j]+P[i-1]*P[k]*P[j];
                    if (thisCost<M[i][j]){
                        M[i][j]=thisCost;
                        S[i][j]=k;
                    }
                }
            }
        }
    }
}
